/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package orgarqsindex.btree;

/**
 *
 * @author Fernando Molon Toigo e Dyoni Bertuol
 */
public class BTreeNode {
    
        private final int TREE_ORDER = 2;
        private final int MAX_KEYS = (int)Math.pow(2, TREE_ORDER);

        private int totalKeys = 0;
        private BTreeNodeKey[] keys;
        private BTreeNode parent;

        public BTreeNode(BTreeNode parent){
            this.keys = new BTreeNodeKey[MAX_KEYS + 1];
            this.parent = parent;
        }
        
        public BTreeNode(BTreeNode parent, BTreeNodeKey[] keys, int totalKeys){
            this(parent);
            this.keys = keys;
            this.totalKeys = totalKeys;
            
            for (int i = 0; i < this.totalKeys; i++){
                BTreeNodeKey key = this.keys[i];
                key.setNode(this);
                
                if (key.getLowerNodes() != null)
                    key.getLowerNodes().parent = this;
                if (key.getHigherNodes() != null)
                    key.getHigherNodes().parent = this;
            }
        }

        public void addKey(BTreeNodeKey newKey){
            if (this.isLeaf())
                this.addOrdered(newKey);
            else
                this.addToChildren(newKey);
        }

        public BTreeNodeKey find(long key){
            for (int i = 0; i < this.totalKeys; i++){
                BTreeNodeKey nodeKey = this.keys[i];
                
                if (nodeKey.getKey() == key){
                    return nodeKey;
                }
                if (key < nodeKey.getKey()){
                    if (nodeKey.getLowerNodes() != null)
                        return nodeKey.getLowerNodes().find(key);
                    else
                        return null;
                }
            }
            
            BTreeNodeKey lastKey = this.keys[totalKeys - 1];
            if (lastKey.getHigherNodes() != null)
                return lastKey.getHigherNodes().find(key);
            else
                return null;
        }

        private boolean isLeaf(){
            for (int i = 0; i < this.totalKeys; i++){
                BTreeNodeKey key = this.keys[i];
                if (key.getLowerNodes() != null)
                    return false;
                
                if (key.getHigherNodes() != null)
                    return false;
            }
            
            return true;
        }
        
        private void addOrdered(BTreeNodeKey newKey){
            int pos;

            newKey.setNode(this);
            if (newKey.getLowerNodes() != null)
                newKey.getLowerNodes().parent = this;
            if (newKey.getHigherNodes() != null)
                newKey.getHigherNodes().parent = this;
            
            for (int i = 0; i < totalKeys; i++){
                
                BTreeNodeKey nodeKey = this.keys[i];
                if (newKey.getKey() < nodeKey.getKey())
                {
                    pos = i;

                    this.insertKey(pos, newKey);

                    if (pos - 1 >= 0 && newKey.getLowerNodes() != null)
                        this.keys[pos - 1].setHigherNodes(newKey.getLowerNodes());

                    if (pos + 1 < this.totalKeys && newKey.getHigherNodes() != null)
                        this.keys[pos + 1].setLowerNodes(newKey.getHigherNodes());
                    
                    if (this.totalKeys > MAX_KEYS)
                        if (this.parent == null)
                            this.splitAsRoot();
                        else
                            this.split();

                    return;
                }
            }

            this.keys[this.totalKeys++] = newKey;

            if (this.totalKeys > 1)
            {
                pos = this.totalKeys - 1;

                this.keys[pos - 1].setHigherNodes(newKey.getLowerNodes());
            }
            
            if (this.totalKeys > MAX_KEYS)
                if (this.parent == null)
                    this.splitAsRoot();
                else
                    this.split();
        }

        private void insertKey(int pos, BTreeNodeKey key){
            for (int i = totalKeys - 1; i >= pos; i--)
                this.keys[i + 1] = this.keys[i];
            
            this.keys[pos] = key;
            this.totalKeys++;
        }
        
        private void addToChildren(BTreeNodeKey newKey){
            
            for (int i = 0; i < this.totalKeys; i++){
                BTreeNodeKey nodeKey = this.keys[i];
                if (newKey.getKey() < nodeKey.getKey()){
                    nodeKey.addLower(newKey);
                    return;
                }
            }

            this.keys[this.totalKeys - 1].addHigher(newKey);
        }

        private void split(){
            int position = this.totalKeys / 2;
            BTreeNodeKey newParent = this.keys[position];
            
            BTreeNodeKey[] highers = new BTreeNodeKey[MAX_KEYS + 1];

            for (int i = position + 1; i < this.totalKeys; i++){
                highers[i - (position + 1)] = this.keys[i];
                this.keys[i] = null;
            }
            this.keys[position] = null;
            
            newParent.setHigherNodes(new BTreeNode(this.parent, highers, this.totalKeys / 2));

            newParent.setLowerNodes(this);
            newParent.getLowerNodes().parent = this.parent;
            
            this.totalKeys -= this.totalKeys / 2 + 1;
            
            this.parent.addOrdered(newParent);
        }

        private void splitAsRoot(){
            int position = this.totalKeys / 2;
            BTreeNodeKey newParent = this.keys[position];

            BTreeNodeKey[] lowers = new BTreeNodeKey[MAX_KEYS + 1];

            for (int i = 0; i < position; i++){
                lowers[i] = this.keys[i];
                this.keys[i] = null;
            }
            
            BTreeNodeKey[] highers = new BTreeNodeKey[MAX_KEYS + 1];
            
            for (int i = position + 1; i < this.totalKeys; i++){
                highers[i - (position + 1)] = this.keys[i];
                this.keys[i] = null;
            }
            
            newParent.setHigherNodes(new BTreeNode(this, highers, this.totalKeys / 2));
            newParent.setLowerNodes(new BTreeNode(this, lowers, this.totalKeys / 2));
            
            this.keys[0] = this.keys[position];
            this.keys[position] = null;
            this.totalKeys = 1;
        }

}
